public class Mergesort {
	
	public static void merge(Integer[] arr, int low, int mid, int high) {
		Integer[] tmp = new Integer[high-low+1];
		int i = low, j = mid+1, k = 0;
		while (i<=mid && j<=high) {
			if (arr[i] <= arr[j]) {
				tmp[k++] = arr[i++];
			} else {
				tmp[k++] = arr[j++];
			}
		}
		// 将上述未处理完数据存入tmp中
		while (i<=mid) tmp[k++] = arr[i++];
		while (j<=high) tmp[k++] = arr[j++];
		
		for (i=0; i<high-low+1; i++) {
			arr[low+i] = tmp[i];
		}
	}
	
	public static void mergesort(Integer[] arr, int low, int high) {
		if (low < high) {
			int mid = (low + high) / 2;
			mergesort(arr, low, mid);
			mergesort(arr, mid+1, high);
			merge(arr, low, mid, high);
		}
	}
	
	public static void main(String[] args) {
		Integer[] arr = {2, 4, 1, 8, 3, 7, 5, 6};
		mergesort(arr, 0, arr.length-1);
		for (int i = 0; i < arr.length; i++) {
			System.out.printf("-%d-", arr[i]);
		}
	}

}